/**
 * 有一个带头结点的单链表，设计一个算法时期元素递增有序
*/
#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
    int data;
    struct LNode* next;
}LNode,*LinkedList;

//初始化
bool init(LinkedList &list);

//插入元素
bool insert(LinkedList &list, int data);

//升序排序
void sort(LinkedList &list);
//显示链表中的元素
void print(LinkedList &list);

int main()
{
    LinkedList list=NULL;
    init(list);
    insert(list,8);
    insert(list,5);
    insert(list,9);
    insert(list,2);
    insert(list,1);
    print(list);
    sort(list);
    print(list);

    return 0;
}

bool init(LinkedList &list)
{
    LNode* newNode=(LNode* )malloc(sizeof(LNode));
    if(!newNode) return false;
    newNode->next=NULL;
    newNode->data=-1;
    list=newNode;
    return true;
}

bool insert(LinkedList &list, int data)
{
    LNode* newNode=(LNode* )malloc(sizeof(LNode));
    if(!newNode) return false;
    newNode->next=NULL;
    newNode->data=data;
    LinkedList node=list;
    while(node->next)
    {
        node=node->next;
    }
    node->next=newNode;
    return true; 
}

void print(LinkedList &list)
{
    LinkedList node=list->next;
    while(node)
    {
        printf("%d ",node->data);
        node=node->next;
    }
}

void sort(LinkedList &list)
{
    LinkedList node=list->next;     //node为遍历结点
    LNode* pre_node=list;           //node的前驱节点,pre_node=node;
    LNode* next_node=node->next;    //node的后继结点,node->next=next_node;

    while(node)
    {
        next_node=node->next;       //next_node结点指向node的后继结点
        pre_node=list;              //node结点默认指向头结点
        while(pre_node && pre_node->next->data<node->data)
        {
            //node结点的前驱结点的值小于node结点的值
            pre_node=pre_node->next;    //前驱结点指向node结点
        }
        node->next=pre_node->next;
        pre_node->next=node;
        node=next_node;
    }

}